home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_400 / 425_01 / tar / deflate.c < prev    next >
Text File  |  1980-07-23  |  30KB  |  802 lines
  1. /*
  2.  The following sorce code is derived from Info-Zip 'zip' 2.01
  3.  distribution copyrighted by Mark Adler, Richard B. Wales,
  4.  Jean-loup Gailly, Kai Uwe Rommel, Igor Mandrichenko and John Bush.
  5. */
  6.  
  7. /*
  8.  *  deflate.c is initially written by Jean-loup Gailly.
  9.  *
  10.  *  PURPOSE
  11.  *
  12.  *      Identify new text as repetitions of old text within a fixed-
  13.  *      length sliding window trailing behind the new text.
  14.  *
  15.  *  DISCUSSION
  16.  *
  17.  *      The "deflation" process depends on being able to identify portions
  18.  *      of the input text which are identical to earlier input (within a
  19.  *      sliding window trailing behind the input currently being processed).
  20.  *
  21.  *      The most straightforward technique turns out to be the fastest for
  22.  *      most input files: try all possible matches and select the longest.
  23.  *      The key feature of this algorithm is that insertions into the string
  24.  *      dictionary are very simple and thus fast, and deletions are avoided
  25.  *      completely. Insertions are performed at each input character, whereas
  26.  *      string matches are performed only when the previous match ends. So it
  27.  *      is preferable to spend more time in matches to allow very fast string
  28.  *      insertions and avoid deletions. The matching algorithm for small
  29.  *      strings is inspired from that of Rabin & Karp. A brute force approach
  30.  *      is used to find longer strings when a small match has been found.
  31.  *      A similar algorithm is used in comic (by Jan-Mark Wams) and freeze
  32.  *      (by Leonid Broukhis).
  33.  *         A previous version of this file used a more sophisticated algorithm
  34.  *      (by Fiala and Greene) which is guaranteed to run in linear amortized
  35.  *      time, but has a larger average cost, uses more memory and is patented.
  36.  *      However the F&G algorithm may be faster for some highly redundant
  37.  *      files if the parameter max_chain_length (described below) is too large.
  38.  *
  39.  *  ACKNOWLEDGEMENTS
  40.  *
  41.  *      The idea of lazy evaluation of matches is due to Jan-Mark Wams, and
  42.  *      I found it in 'freeze' written by Leonid Broukhis.
  43.  *      Thanks to many info-zippers for bug reports and testing.
  44.  *
  45.  *  REFERENCES
  46.  *
  47.  *      APPNOTE.TXT documentation file in PKZIP 1.93a distribution.
  48.  *
  49.  *      A description of the Rabin and Karp algorithm is given in the book
  50.  *         "Algorithms" by R. Sedgewick, Addison-Wesley, p252.
  51.  *
  52.  *      Fiala,E.R., and Greene,D.H.
  53.  *         Data Compression with Finite Windows, Comm.ACM, 32,4 (1989) 490-595
  54.  *
  55.  *  INTERFACE
  56.  *
  57.  *      int lm_init(void)
  58.  *          Initialize the "longest match" routines for a new file
  59.  *
  60.  *      int fast_deflate(char*, unsigned)
  61.  *      int lazy_deflate(char*, unsigned)
  62.  *          Processes a new input file and return its compressed length. Sets
  63.  *          the compressed length, crc, deflate flags and internal file
  64.  *          attributes.
  65.  */
  66.  
  67. #include <stdio.h>
  68. #include "modern.h"
  69. #include "zalloc.h"
  70. #include "zippipe.h"
  71. #include "zipdefs.h"
  72. #include "zipguts.h"
  73. #ifdef MODERN
  74. #  include <string.h>
  75. #else
  76. #  ifdef pyr /* Pyramid */
  77. #    define ZMEM /* No mem???() functions at all */
  78. #  endif
  79. #endif
  80.  
  81. /* Define this symbol if your target allows access to unaligned data.
  82.  * This is not mandatory, just a speed optimization. The compressed
  83.  * output is strictly identical.
  84.  */
  85. #ifndef UNALIGNED_OK
  86. #  ifdef MSDOS
  87. #   ifndef WIN32
  88. #    define UNALIGNED_OK
  89. #   endif
  90. #  endif
  91. #  ifdef i386
  92. #    define UNALIGNED_OK
  93. #  endif
  94. #  ifdef mc68020
  95. #    define UNALIGNED_OK
  96. #  endif
  97. #  ifdef vax
  98. #    define UNALIGNED_OK
  99. #  endif
  100. #endif
  101.  
  102. /* Compile with MEDIUM_MEM to reduce the memory requirements or
  103.  * with SMALL_MEM to use as little memory as possible. Use BIG_MEM if the
  104.  * entire input file can be held in memory (not possible on 16 bit systems).
  105.  * Warning: defining these symbols affects HASH_BITS (see below) and thus
  106.  * affects the compression ratio. The compressed output
  107.  * is still correct, and might even be smaller in some cases.
  108.  */
  109.  
  110. #ifdef SMALL_MEM
  111. #   define HASH_BITS  13  /* Number of bits used to hash strings */
  112. #endif
  113. #ifdef MEDIUM_MEM
  114. #   define HASH_BITS  14
  115. #endif
  116. #ifndef HASH_BITS
  117. #   define HASH_BITS  15
  118.    /* For portability to 16 bit machines, do not use values above 15. */
  119. #endif
  120.  
  121. #define HASH_SIZE (unsigned)(1<<HASH_BITS)
  122. #define HASH_MASK (HASH_SIZE-1)
  123. #define WMASK     (WSIZE-1)
  124. /* HASH_SIZE and WSIZE must be powers of two */
  125.  
  126. #define NIL 0
  127. /* Tail of hash chains */
  128.  
  129. #ifndef TOO_FAR
  130. #  define TOO_FAR 4096
  131. #endif
  132. /* Matches of length 3 are discarded if their distance exceeds TOO_FAR */
  133.  
  134. #ifdef ATARI_ST
  135. #  undef MSDOS /* avoid the processor specific parts */
  136.    /* (but the Atari should never define MSDOS anyway ...) */
  137. #endif
  138. #ifdef MSDOS
  139. #  ifndef NO_ASM
  140. #    ifndef ASMV
  141. #      define ASMV
  142. #    endif
  143. #  endif
  144. #endif
  145. #ifdef ASMV
  146. #  ifndef MSDOS
  147. #    ifdef DYN_ALLOC
  148.        #error: DYN_ALLOC not yet supported in match.s
  149. #    endif
  150. #  endif
  151. #endif
  152. #ifdef MSDOS
  153. #  ifndef __32BIT__
  154. #    define MAXSEG_64K
  155. #  endif
  156. #endif
  157.  
  158. /* Local data used by the "longest match" routines. */
  159.  
  160. #if defined(BIG_MEM) || defined(MMAP)
  161.   typedef unsigned Pos; /* must be at least 32 bits */
  162. #else
  163.   typedef ush Pos;
  164. #endif
  165. typedef unsigned IPos;
  166. /* A Pos is an index in the character window. We use short instead of int to
  167.  * save space in the various tables. IPos is used only for parameter passing.
  168.  */
  169.  
  170. #ifndef DYN_ALLOC
  171.   uch    window[2L*WSIZE];
  172.   /* Sliding window. Input bytes are read into the second half of the window,
  173.    * and move to the first half later to keep a dictionary of at least WSIZE
  174.    * bytes. With this organization, matches are limited to a distance of
  175.    * WSIZE-MAX_MATCH bytes, but this ensures that IO is always
  176.    * performed with a length multiple of the block size. Also, it limits
  177.    * the window size to 64K, which is quite useful on MSDOS.
  178.    * To do: limit the window size to WSIZE+BSZ if SMALL_MEM (the code would
  179.    * be less efficient since the data would have to be copied WSIZE/BSZ times)
  180.    */
  181.   Pos    prev[WSIZE];
  182.   /* Link to older string with same hash index. To limit the size of this
  183.    * array to 64K, this link is maintained only for the last 32K strings.
  184.    * An index in this array is thus a window index modulo 32K.
  185.    */
  186.   Pos    head[HASH_SIZE];
  187.   /* Heads of the hash chains or NIL. If your compiler thinks that
  188.    * HASH_SIZE is a dynamic value, recompile with -DDYN_ALLOC.
  189.    */
  190. #else
  191.    uch  far *window = NULL;
  192.    Pos  far *prev   = NULL;
  193.    Pos  far *head   = NULL;
  194. #endif
  195. #ifndef zalloc
  196.    void far *p_win  = NULL;
  197.    void far *p_prev = NULL;
  198.    void far *p_head = NULL;
  199. #else
  200. #  define p_win  window
  201. #  define p_prev prev
  202. #  define p_head head
  203. #endif
  204.  
  205. #define WINDOW_SIZE ((ulg)2*WSIZE)
  206.  
  207. long block_start;
  208. /* window position at the beginning of the current output block. Gets
  209.  * negative when the window is moved backwards. */
  210.  
  211. static unsigned ins_h;  /* hash index of string to be inserted */
  212. static char uptodate;   /* hash preparation flag */
  213.  
  214. #define H_SHIFT  ((HASH_BITS+MIN_MATCH-1)/MIN_MATCH)
  215. /* Number of bits by which ins_h and del_h must be shifted at each
  216.  * input step. It must be such that after MIN_MATCH steps, the oldest
  217.  * byte no longer takes part in the hash key, that is:
  218.  *   H_SHIFT * MIN_MATCH >= HASH_BITS */
  219.  
  220. unsigned int prev_length;
  221. /* Length of the best match at previous step. Matches not greater than this
  222.  * are discarded. This is used in the lazy match evaluation. */
  223.  
  224.        unsigned strstart;    /* start of string to insert */
  225.        unsigned match_start; /* start of matching string */
  226. static unsigned lookahead;   /* number of valid bytes ahead in window */
  227.        unsigned minlookahead;
  228.  
  229. unsigned max_chain_length;
  230. /* To speed up deflation, hash chains are never searched beyond this length.
  231.  * A higher limit improves compression ratio but degrades the speed. */
  232.  
  233. static unsigned int max_lazy_match;
  234. /* Attempt to find a better match only when the current match is strictly
  235.  * smaller than this value. This mechanism is u